package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20241006;

public class leetcode3312 {
    /**
     * 查询排序后的最大公约数：枚举+容斥+前缀和+二分
     * @param nums
     * @param queries
     * @return
     */
    public int[] gcdValues(int[] nums,long[] queries){
        int mx=0;
        for(int x : nums){
            mx=Math.max(mx,x);
        }
        int[] cntX=new int[mx+1];
        for(int x : nums){
            cntX[x]++;
        }

        long[] cntGcd=new long[mx+1];
        for(int i=mx;i>0;i--){
            int c=0;
            for(int j=i;j<=mx;j+=i){
                c+=cntX[j];
                cntGcd[i]-=cntGcd[j];// gcd是2i,3i,4i,...,的数对不能统计进来
            }
            cntGcd[i]+=(long)c*(c-1)/2;// c个数选2个，组成c*(c-1)/2个数对
        }

        for(int i=2;i<=mx;i++){
            cntGcd[i]+=cntGcd[i-1];// 原地求前缀和
        }

        int[] ans=new int[queries.length];
        for(int i=0;i<queries.length;i++){
            ans[i]=upperBound(cntGcd,queries[i]);
        }
        return ans;
    }

    private int upperBound(long[] nums,long target){
        int left=-1,right=nums.length;// 开区间(left,right)
        while(left+1<right){
            int mid=(left+right)>>>1;
            if(nums[mid]>target){
                right=mid;
            }else{
                left=mid;
            }
        }
        return right;
    }
}
